package com.atguigu.practice;

import java.util.Scanner;

public class LevenshteinDistance {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String word1=scanner.next();
        String word2=scanner.next();
                int n = word1.length();
                int m = word2.length();

                // 有一个字符串为空串
                if (n * m == 0) {
                    System.out.println(n+m);
                    return;
                }

                // DP 数组
                int[][] D = new int[n + 1][m + 1];

                // 边界状态初始化
                for (int i = 0; i < n + 1; i++) {
                    D[i][0] = i;
                }
                for (int j = 0; j < m + 1; j++) {
                    D[0][j] = j;
                }

                // 计算所有 DP 值
                for (int i = 1; i < n + 1; i++) {
                    for (int j = 1; j < m + 1; j++) {
                        int left = D[i - 1][j] + 1;
                        int down = D[i][j - 1] + 1;
                        int left_down = D[i - 1][j - 1];
                        if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                            left_down += 1;
                        }
                        D[i][j] = Math.min(left, Math.min(down, left_down));
                    }
                }
        System.out.println(D[n][m]);
            }
        }
